package DoublyLinked;

/**
 * Created by sunwei on 2017/10/10
 * Time:17:34
 */
public class DoublyLinked {
    private Link first;
    private Link last;
    /*
    构造函数
     */
    public DoublyLinked() {
        first = null;
        last = null;
    }

    /*
    双向链表，进行判断是否为空
     */
    public boolean isEmpty(){
        return (first==null);
    }

    /*
    从链表的头部添加节点：添加节点有两种方式：在表头插入，在表尾插入
     */
    public void insertFirst(long key) {
        Link newLink = new Link(key);
        if (isEmpty()) {
            //如果链表是空的，则将last指向newLink，即将newLink直接放到链表中
            last = newLink;
        } else {
            //如果链表不是空的，那么就直接在表头加入就好了
            first.previous = newLink;
        }
        newLink.next =first;
        first = newLink;
    }

        /*
        从链表的尾部加入节点
         */
        public void insertLast(long key){
            Link newlink = new Link(key);
            if (isEmpty()) {
                  first = newlink;
            }else {
                newlink.previous = last;
                last.next = newlink;
            }
            last = newlink;
    }

    /*
    删除首节点
     */
    public Link deleteFirst(){
        Link temp = first;
        if (first.next == null) {//如果链表是空的那么就直接将last置为空就可以了
              last = null;
        }else {
            first.next.previous = null;
        }
        first = first.next;
        return temp;
    }

    /*
    删除尾节点
     */
    public Link deleteLast(){
        Link temp = last;
        //如果只有一个节点那么直接让first置空就可以了
        if (first.next==null) {
              first=null;
        }else {
            //如果至少有两个节点
            last.previous.next = null;
        }
        last = last.previous;
        return temp;
    }

    /*
    在特定的元素里面插入数据
     */
    public boolean insertAfter(long key,long dd){
        Link current = first;
        //下面这个循环就是去寻找有没有与Key值相对应的节点
        while (current.dData!=key){
            current = current.next;
            if (current==null) {//如果没有一个节点的值等于key则说明没找到，那么就返回false
                return false;
            }
        }
        Link newLink = new Link(dd);
        //如果到这一步，则说明找到了current节点，但是还有一个问题找到的current节点有几种情况：在链表头部、中间、尾部
        //因此要分别进行讨论
        if (current==last) {//如果是最后一个节点，那么要单独讨论
            //直接将新节点的前引用指向current
           newLink.previous =current;
           //在将last引用指向newLink节点
           last = newLink;
        }else {
            //将新添加的节点的后引用指向原来节点的后节点
            newLink.next = current.next;
            //将原来的节点前引用指向新添加的节点
            current.next.previous = newLink;
        }
        newLink.previous= current;
        current.next = newLink;
        return true;
    }

    /*
    根据输入的元素值，删除相应的元素
     */
    public Link deleteKey(long key){

        Link current = first;
        while (current.dData!=key){
            current = current.next;
            if (current.next==null) {
                  return null;
            }
        }
        //循环找出的节点可以是首节点、链表中间节点、尾节点等等，因此要分别讨论
        if (current==first) {
              first = current.next;
        }else {
            current.previous.next=current.next;
        }
        if (current==last) {
              last = current.previous;
        }  else {
            current.previous.next = current.next;
        }
        return current;
    }

    /*
    从前往后遍历显示链表
     */
    public void displayForward(){
        System.out.print("List(first--->last)");
        Link current = first;
        while (current!=null){
            current.displayLink();
            current = current.next;
        }
        System.out.println(" ");
    }

    /*
    从后往前遍历显示链表
     */
    public void displayBackward(){
        System.out.print("List(last-->first");
        Link current = last;
        while (current!=null){
            current.displayLink();
            current =current.previous;
        }
        System.out.println(" ");
    }





}
